package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.LinkedList;

public class _125_swipe_landmine {
    
    /**
     * 我他吗被变量名给阴了
     * */
    static class bfs {
        int[] dirX = {1, 1, 0, -1, -1, -1, 0, 1};
        int[] dirY = {0, 1, 1, 1, 0, -1, -1, -1};
        public char[][] updateBoard(char[][] board, int[] click) {
            int clickX = click[0], clickY = click[1];
            if (board[clickX][clickY] == 'M') board[clickX][clickY] = 'X';
            else {
                int m = board.length, n = board[0].length;
                LinkedList<int[]> q = new LinkedList<>();
                boolean[][] visited = new boolean[m][n];
                visited[clickX][clickY] = true;
                q.offer(new int[]{clickX, clickY});
                while (!q.isEmpty()) {
                    int[] xy = q.poll();
                    int x = xy[0], y = xy[1];
                    int mines = 0;
                    for (int i = 0; i < 8; i++) {
                        int nextX = x + dirX[i], nextY = y + dirY[i];
                        if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n || visited[nextX][nextY]) continue;
                        if (board[nextX][nextY] == 'M') mines++;
                    }
                    if (mines > 0) board[x][y] = (char) (mines + '0');
                    else {
                        board[x][y] = 'B';
                        for (int i = 0; i < 8; i++) {
                            int nextX = x + dirX[i], nextY = y + dirY[i];
                            if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n || board[nextX][nextY] != 'E' || visited[nextX][nextY]) continue;
                            q.offer(new int[] {nextX, nextY});
                            visited[nextX][nextY] = true;
                        }
                    }
                }
            }
            return board;
        }
    }
    
    /**
     * 还是 dfs 快啊
     * */
    static class dfs {
        int[] dirx = {0, 0, 1, 1, 1, -1, -1, -1};
        int[] diry = {1, -1, 1, 0, -1, 1, 0, -1};
        public char[][] updateBoard(char[][] board, int[] click) {
            int x = click[0], y = click[1];
            if (board[x][y] == 'M') board[x][y] = 'X';
            else {
                boolean[][] visited = new boolean[board.length][board[0].length];
                visited[x][y] = true;
                dfs(board, x, y, visited);
            }
            return board;
        }
        void dfs(char[][] board, int x, int y, boolean[][] visited) {
            int mines = 0;
            for (int i = 0; i < 8; i++) {
                int newx = x + dirx[i], newy = y + diry[i];
                if (newx < 0 || newy < 0 || newx >= board.length || newy >= board[0].length || visited[newx][newy])
                    continue;
                if (board[newx][newy] == 'M')
                    mines++;
            }
            if (mines > 0) board[x][y] = (char) (mines + '0');
            else {
                board[x][y] = 'B';
                for (int i = 0; i < 8; i++) {
                    int newx = x + dirx[i], newy = y + diry[i];
                    if (newx < 0 || newy < 0 || newx >= board.length || newy >= board[0].length || board[newx][newy] != 'E' || visited[newx][newy])
                        continue;
                    visited[newx][newy] = true;
                    dfs(board, newx, newy, visited);
                }
            }
        }
    }
}
